package demo1;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Spider-Man
 * Date: 2024-03-25
 * Time: 15:44
 */
//顺序表
public class SeqList {
    private int[] elem;
    private int usedSize; //记录顺序表中元素的有效个数
    private static final int DEFAULT_CAPACITY = 5;//数组大小的默认值
    //加static是使所有顺序表默认数组大小都是10；

    public SeqList() {
        //构造方法，初始化数组
        this.elem = new int[DEFAULT_CAPACITY];
    }

    //打印顺序表,该方法并不是顺序表中的方法
    public void display() {
        for(int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

    //新增数据，默认在数据最后进行新增
    public void  add(int data) {
        //需要考虑此时数组是否为满
        if(isfull()) {
            //进入到里面来，说明此时数组满了，需要进行扩容
            // elem = Arrays.copyOf(elem,elem.length*2);将原数组扩容为原数组的二倍
            resize();
        }
        this.elem[usedSize] = data;
        usedSize++;
    }
    //判断数组是否为满
    public boolean isfull() {
        return usedSize == elem.length;
        //因为可能进行过扩容，所以需要进行length去计算
    }

    //判定是否包含某个元素
    public boolean contains(int toFind) {
        for(int i = 0; i < usedSize; i++) {
            //可能是引用类型进行比较，所以需要是有squals进行比较，返回值是boolean类型的
            if(elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }
    //查找某个元素对应的位置
    public int indexOf(int toFind) {
        //可能数组当中存放的是引用类型
        for(int i = 0; i < this.usedSize; i++) {
            if(elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    //获取 pos 位置的元素
    public int get (int pos) {
        if(pos < 0 || pos >= usedSize) {
            throw new RuntimeException("get 获取数据时，位置不合法");
        }
        return elem[pos];
    }
    //判断数组为空
    public boolean isEmpty() {
         return usedSize == 0;
    }
    //获取顺序表的长度
    public int size() {
        return this.usedSize;
    }
    //给pos位置元素设置value[更新的意思]
    public void set(int pos,int value) {
        //需要判断pos是否合法
        if(checkPos(pos)) {
            throw new PosOutBoundsException("set 数据时，位置不合法！");
        }
        this.elem[pos] = value;
    }

    //检测pos位置是否合法
    private boolean checkPos(int pos) {
        if(pos < 0 || pos >= this.usedSize) {
            return false;
        }
        return true;
    }


    //并不能随意位置插入，插入位置的前面一定是有元素的
    public void add(int pos,int data) {
        if(pos < 0 || pos > this.usedSize) {
            throw new PosOutBoundsException("add 元素的时 位置不合法！");
        }

        //判断是否需要扩容
        if(isfull()) {
            resize();
        }
        /*this.elem[pos] = data;
        usedSize++;*/ // 错误的，这个代码是默认pos就是最后的位置
        //可能插入位置已经有数据了
        //挪数据
        for(int i = this.usedSize -1; i >= pos; i++) {
            this.elem[i+1] = this.elem[i];
        }
        //存数据
        this.elem[pos] = data;
        this.usedSize++;
    }
    //数据扩容
    private void resize() {
        elem = Arrays.copyOf(elem,2*elem.length);
    }

    //删除第一次出现的关键字KEY
    public void remove(int key) {
        //需要判空
        if (isEmpty()) {
            return;
        }
        //indexof(key)  索引第一次出现key的位置，并且返回下标,没有找到key则返回-1
        int index = indexOf(key);
        if(index == -1) {
            return;
        }
        //顺序表中存在key
        for(int i = index; i < usedSize -1; i++) {
             this.elem[i] = this.elem[i+1];
        }
        usedSize--;
    }

    public void clear() {
        //顺序表中存放的时引用类型时，需要遍历数组将每个元素都置空
        /*for(int i = 0; i < usedSize; i++) {
            this.elem[i]  = null;
        }
        usedSize = 0;*/
        //引用类型必须要置空，如果直接进行将usedSize等于0,数组任然是在使用的，不置空的话数组中的引用还是会占用内存
        usedSize = 0;
        return ;
    }

}
